package com.LeeCode;

import java.util.*;

/**
 * 图的最大边权的最小值
 */

public class Code3419 {
    public static void main(String[] args) {
        int[][] edges = {
                {1, 2, 1},
                {1, 3, 3},
                {1, 4, 5},
                {2, 3, 2},
                {3, 4, 2},
                {4, 0, 1}
        };
        int n = 5, threshold = 1;
        System.out.println(new Code3419().minMaxWeight(n, edges, threshold));

    }

    public int minMaxWeight(int n, int[][] edges, int threshold) {
        int max = 0;
        List<int[]>[] graph = new List[n];
        Arrays.setAll(graph, i -> new ArrayList<>());

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[v].add(new int[]{u, w});
            max = Math.max(max, w + 1);
        }


        int left = 0, right = max;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(graph, mid))
                right = mid;
            else
                left = mid;
        }

        return right == max ? -1 : right;
    }

    private boolean check(List<int[]>[] graph, int limit) {
        boolean[] visited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();

        if (!graph[0].isEmpty()) {
            queue.add(0);
            visited[0] = true;
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int[] neighbor : graph[u]) {
                int v = neighbor[0], w = neighbor[1];
                if (w <= limit && !visited[v]) {
                    visited[v] = true;
                    queue.add(v);
                }
            }
        }

        for (boolean v : visited) {
            if (!v) return false;
        }
        return true;
    }
}
